struct Node* copyRandomList(struct Node* head) 
{
	struct Node*cur = head;
    while(cur)
    {
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        struct Node*next = cur->next;
        copy->val = cur->val;
        cur->next = copy;
        copy->next = next;
        cur = next;
    }
    cur = head;
    while(cur)
    {
        struct Node*copy = cur->next;
        if(cur->random != NULL)
        {
            copy->random = cur->random->next;
        }
        else
        {
            copy->random = NULL;
        }
        cur = copy->next;
    }
    cur = head;
    struct Node*copyhead = NULL, *tail = NULL;
    while(cur)
    {
        struct Node* copy = cur->next
        struct Node* next = copy->next;
        if(tail == NULL)
        {
            copyhead = tail = copy;
        }
        else
        {
            tail->next = copy;
            tail = tail->next;
        }
        cur->next = next;
        cur = next;
    }
    return copyhead;
}